package leetcode.offer;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _25_K个一组翻转链表 {

    /**
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[2,1,4,3,5]
     * 不足k个的部分按原序返回
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode dummyNode = new ListNode(0);
        ListNode node = dummyNode;
        // 翻转局部头结点
        ListNode localHead = head;
        // 翻转局部尾结点
        ListNode tailNode = head;
        while (tailNode != null) {
            // 找到要翻转部分的尾结点
            for (int i = 0; i < k - 1; i++) {
                tailNode = tailNode.next;
                // 不足k个结点的情况
                if (tailNode == null) {
                    node.next = localHead;
                    return dummyNode.next;
                }
            }
            // 记录下一个要翻转的局部头结点
            ListNode temp = tailNode.next;
            // 断开局部结点与原链表的指针
            tailNode.next = null;
            // 局部翻转并连接新链表
            node.next = reverse(localHead);
            // 原链表的头部作为新链表的尾部
            node = localHead;
            // 开始翻转下一个局部链表
            localHead = temp;
            tailNode = temp;
        }
        return dummyNode.next;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode node = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}
